DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2010.61

Vertex Disjoint Paths for Dispatching in Railways

Authors: Holger Flier, Matús Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract

We study variants of the vertex disjoint paths problem in planar graphs where paths have to be selected from a given set of paths. We study the problem as a decision, maximization, and routing-in-rounds problem. Although all considered variants are NP-hard in planar graphs, restrictions on the location of the terminals, motivated by railway applications, lead to polynomially solvable cases for the decision and maximization versions of the problem, and to a $p$-approximation algorithm for the routing-in-rounds problem, where $p$ is the maximum number of alternative paths for a terminal pair.

Cite as

Holger Flier, Matús Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych. Vertex Disjoint Paths for Dispatching in Railways. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 61-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{flier_et_al:OASIcs.ATMOS.2010.61,
  author =	{Flier, Holger and Mihal\'{a}k, Mat\'{u}s and Sch\"{o}bel, Anita and Widmayer, Peter and Zych, Anna},
  title =	{{Vertex Disjoint Paths for Dispatching in Railways}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{61--73},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.61},
  URN =		{urn:nbn:de:0030-drops-27508},
  doi =		{10.4230/OASIcs.ATMOS.2010.61},
  annote =	{Keywords: algorithms, approximation, complexity, graph theory, railways, routing, transportation}
}

Search Results

Documents authored by Zych, Anna

Vertex Disjoint Paths for Dispatching in Railways

Abstract

Cite as

Thanks for your feedback!

Could not send message